public class test4 {

    // https://leetcode.cn/problems/reverse-pairs/submissions/679592148/


}
class Solution1 {
    int[] tmp;
    public int reversePairs(int[] nums) {
        int n=nums.length;
        tmp=new int[n];
        return mergeSort(nums,0,n-1);
    }
    public int mergeSort(int[] nums,int left,int right) {
        int ret=0;
        if(left>=right) return 0;
        int mid=(left+right)/2;
        ret+=mergeSort(nums,left,mid);
        ret+=mergeSort(nums,mid+1,right);
        int cur1=left,cur2=mid+1,k=0;
        while(cur1<=mid && cur2<=right) {
            while(cur1<=mid && nums[cur2]>=nums[cur1]/2.0) cur1++;
            if(cur2>right) break;
            ret+=(mid-cur1+1);
            cur2++;
        }
        // 合并逻辑
        cur1=left;cur2=mid+1;
        while(cur1<=mid && cur2<=right) {
            if(nums[cur1]<=nums[cur2]) {
                tmp[k++]=nums[cur1++];
            } else {
                tmp[k++]=nums[cur2++];
            }
        }
        while(cur1<=mid) tmp[k++]=nums[cur1++];
        while(cur2<=right) tmp[k++]=nums[cur2++];
        // 将tmp复制回原数组
        for(int i=left;i<=right;i++) {
            nums[i]=tmp[i-left];
        }
        return ret;
    }
}
